#pragma once
#include <algorithm>
#include "Graph.h"

void changevalues(std::vector<int> & values, int from, int to){ // замена всех равных from на to в values
	for (int i = 0; i < values.size(); i++)
	if (values[i] == from)
		values[i] = to;
}

int dfs_Tar(Graph &g, int v, std::vector<int> & indexes, int & cnt){ // DFS для алгоритма Тарьяна
	g.setcolor(v, 1);
	indexes[v] = cnt++;
	std::vector<e> edges = g.get_vertex(v).get_edges();
	for (unsigned int i = 0; i < edges.size(); i++)
	if (g.checkcolor((*(edges[i].next)).get_id()) == 0){
		int returned = dfs_Tar(g, (*(edges[i].next)).get_id(), indexes, cnt);
		if (indexes[v] > returned)
			changevalues(indexes, indexes[v], returned);
	}
	else if (indexes[v] > indexes[(*(edges[i].next)).get_id()])
		changevalues(indexes, indexes[v], indexes[(*(edges[i].next)).get_id()]);
	g.setcolor(v, 2);
	return indexes[v];
}

void printCompAns(std::vector<std::vector<int>> answer){ // вывод ответа
	std::cout << answer.size() << std::endl;
	for (int i = 0; i < answer.size(); i++){
		for (int j = 0; j < answer[i].size(); j++)
			std::cout << answer[i][j] << ' ';
		std::cout << std::endl;
	}
}

void Tarjan(){
	int N = -1;
	std::ifstream fin("input.txt");
	Graph gr = Graph();
	std::vector< std::vector<int> > edges;
	int f, t;
	while (!fin.eof()){ // считали список ребер
		fin >> f >> t;
		std::vector<int> tmp;
		tmp.push_back(f);
		tmp.push_back(t);
		edges.push_back(tmp);
		if (N < std::max(f, t))
			N = std::max(f, t);
	}
	N++; // кол-во вершин графа
	gr.set_size(N);
	for (auto it = edges.begin(); it != edges.end(); it++){ // добавили ребра в граф
		gr.add_edge((*it)[0], (*it)[1], 1);
	}
	// собственно, алгоритм Тарьяна
	gr.reiterate();
	std::vector<int> indexes;
	std::vector<int> indexcounter;
	std::vector<std::vector<int>> answer;
	indexes.assign(N, N);
	indexcounter.assign(N, 0);
	for (int i = 0; i < N; i++){
		int cnt = 0;
		if (gr.checkcolor(i) == 0)
			dfs_Tar(gr, i, indexes, cnt);
		if (cnt != 0){
			for (int j = 0; j < N; j++)
			if (indexes[j] != N)
				indexcounter[indexes[j]]++;
			for (int j = 0; j < N; j++)
			if (indexcounter[j] > 0){
				answer.push_back(std::vector<int>());
				for (int k = 0; k < N; k++)
					if (indexes[k] == j)
						answer[answer.size() - 1].push_back(k);
			}
		}
		indexes.assign(N, N);
		indexcounter.assign(N, 0);
	}
	printCompAns(answer);
	fin.close();
}